#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

Tree *printCommonAncestor(Tree *root, int a, int b, vector<int> &ans)
{
   if (!root) return NULL;
   if (root->data == a || root->data == b) return root;
   Tree *l = printCommonAncestor(root->left, a, b, ans);
   Tree *r = printCommonAncestor(root->right, a, b, ans);
   if (l && r) {
       ans.push_back(root->data);
       return root;
   }
   if (l) {if (l->data != a) ans.push_back(root->data); return l;}
   if (r) {if (r->data != b) ans.push_back(root->data); return r;}
}


int main(int argc, char **argv)
{
    int input[] = {25, 5,6,7,8,23,14,16,1,7,24,26,27,56,45,7,5,6,3,2,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    vector<Tree *> result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    print_ascii_tree(root);
    vector<int> ans;
    printCommonAncestor(root, 10, 24, ans);
    for (int i = 0; i < ans.size(); i++) {
	cout << ans[i] << " ";
    }
}
